786B - Legacy - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pii pair <int, int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back

const int NM = 1e5, INF = 1e18+7;

struct node{
	int lchild, rchild, w;
};

struct vertex{
	int u, w;
	vertex(int a, int b){
		u = a, w = b;
	}
};

struct cmp{
	bool operator()(vertex a, vertex b){
		return a.w > b.w;
	}
};

int n, q, s, res[NM+5];
node st[7*NM+5];
vector <pii> adj[7*NM+5];
int nNode, root1, root2;
priority_queue <vertex, vector <vertex>, cmp> Q;
bool mark[7*NM+5];

int build(int type, int l, int r){
	int cur = ++nNode;
	st[cur].w = +INF;
	if (r-l+1 == 2){
		st[cur].lchild = l, st[cur].rchild = r;
	}
	else if (r-l+1 == 3){
		st[cur].lchild = build(type, l, l+1), st[cur].rchild = r;
	}
	else{
		int mid = (l+r)/2;
		st[cur].lchild = build(type, l, mid);
		st[cur].rchild = build(type, mid+1, r);
	}
	if (type == 2){
		adj[cur].pb(mp(st[cur].lchild, 0));
		adj[cur].pb(mp(st[cur].rchild, 0));
	}
	else{
		adj[st[cur].lchild].pb(mp(cur, 0));
		adj[st[cur].rchild].pb(mp(cur, 0));
	}
	return cur;
}

void query(int type, int id, int tl, int tr, int v, int l, int r, int w){
	if (r < tl || l > tr) return;
	if (tl >= l && tr <= r){
		if (type == 2)
			adj[v].pb(mp(id, w));
		else
			adj[id].pb(mp(v, w));
		return;
	}
	int mid = (tl+tr)/2;
	query(type, st[id].lchild, tl, mid, v, l, r, w);
	query(type, st[id].rchild, mid+1, tr, v, l, r, w);
}

void dijkstra(){
	Q.push(vertex(s, 0));
	while (true){
		while (!Q.empty() && mark[Q.top().u]) Q.pop();
		if (Q.empty()) break;
		int u = Q.top().u;
		Q.pop();
		mark[u] = 1;
		if (u <= n) res[u] = st[u].w;
		for (int i = 0; i < adj[u].size(); i++){
			int v = adj[u][i].fi;
			if (!mark[v] && st[u].w+adj[u][i].se < st[v].w){
				st[v].w = st[u].w+adj[u][i].se;
				Q.push(vertex(v, st[v].w));
			}
		}
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q >> s;
	if (n == 1){
		cout << "0 ";
		return 0;
	}
	for (int i = 1; i <= n; i++)
		st[i].w = +INF;
	st[s].w = 0;
	nNode = n;
	root1 = build(2, 1, n);
	root2 = build(3, 1, n);
	while (q--){
		int t, v, u, l, r, w;
		cin >> t;
		if (t == 1){
			cin >> v >> u >> w;
			adj[v].pb(mp(u, w));
		}
		else{
			cin >> v >> l >> r >> w;
			if (t == 2) query(2, root1, 1, n, v, l, r, w);
			else query(3, root2, 1, n, v, l, r, w);
		}
	}
	for (int i = 1; i <= n; i++)
		res[i] = -1;
	dijkstra();
	for (int i = 1; i <= n; i++)
		cout << res[i] << ' ';
	return 0;
}